package jianzhioffer;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Author: Zhang Dongwei
 * Date: 2023/3/24 15:20
 * 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
 *
 * 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
 */
public class offer_57_ii_和为s的连续正数序列 {

    public static void main(String[] args) {
//        int[][] nu = {{1, 2, 3}, {4, 5}};


        int target = 9;
        int[][] nums = findContinuousSequence(target);
        for (int i=0; i<nums.length; i++){
            System.out.println(Arrays.toString(nums[i]));
        }
    }

//    自己暴力解法，有问题；
//    public static int[][] findContinuousSequence1(int target) {
//        int count=0, flag=0;
//        int[][] res;
//        for (int i=1; i<=(target+1)/2; i++){
//            for (int j=i+1; j<=(target+1)/2; j++){
//                if (((i+j)*(j-i+1))/2==target && ((i+j)*(j-i+1))%2==0){
//                    res[count] = new int[j-i+1];
//                }
//            }
//        }
//        return new int[2][3];
//    }

//和上面的思想类似，一些细节不太会实现(公式法)
    public static int[][] findContinuousSequence2(int target) {
        int i=1;
        double j=2.0;
        List<int []> res = new ArrayList<>();
        while (i<j){
            j = (-1+Math.sqrt(1+4*(2*target+(long)i*i-i)))/2;
            if (i<j&&j==(int)j){
                int[] ans = new int[(int)j-i+1];
                for (int k=i; k<=(int)j; k++)
                    ans[k-i] = k;
                res.add(ans);
            }
            i++;
        }
        return res.toArray(new int[0][]);
    }

//    滑动窗口
    public static int[][] findContinuousSequence(int target) {
        int i = 1, j = 2, s = 3;
        List<int[]> res = new ArrayList<>();
        while(i < j) {
            if(s == target) {
                int[] ans = new int[j - i + 1];
                for(int k = i; k <= j; k++)
                    ans[k - i] = k;
                res.add(ans);
            }
            if(s >= target) {
                s -= i;
                i++;
            } else {
                j++;
                s += j;
            }
        }
        return res.toArray(new int[0][]);
    }
}
